package com.leetcodehot.problems;

import java.util.Arrays;

public class problems1143 {
    /**
     * 1143题出现了DP公式无法完全替换为正序或者倒序的情况，对于这种情况一般情况下是
     * 针对f[i + 1][j + 1]而言f[i][j]替换为pre，其他两种情况都是可以继续正序处理，这样就实现了最终转化为一维f[n]来处理。
     */
    /**
     * 记忆化搜索
     */
    /*
    public int longestCommonSubsequence(String text1, String text2) {
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();
        int m = char1.length;
        int n = char2.length;
        int[][] memo = new int[m + 1][n + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(m - 1, n - 1, char1, char2, memo);
    }

    private int dfs(int i, int j, char[] char1, char[] char2, int[][] memo) {
        if (i < 0 || j < 0) {
            return 0;
        }
        if (memo[i][j] != -1) return memo[i][j];
        if (char1[i] == char2[j]) {
            return memo[i][j] = dfs(i - 1, j - 1, char1, char2, memo) + 1;
        }
        //不选
        int ans = Math.max(dfs(i - 1, j, char1, char2, memo), dfs(i, j - 1, char1, char2, memo));
        //由算法推出可知 都已经不同的情况下 不需要下面这步 已经在上面这里算过此结果了
        //ans = Math.max(ans, dfs(i - 1, j - 1, char1, char2, memo));
        return memo[i][j] = ans;
    }
    */

    /**
     * 递推
     */
    /*
    public int longestCommonSubsequence(String text1, String text2) {
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();
        int m = char1.length;
        int n = char2.length;
        int[][] f = new int[m + 1][n + 1];
        f[0][0] = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (char1[i] == char2[j]) {
                    f[i + 1][j + 1] = f[i][j] + 1;
                } else {
                    f[i + 1][j + 1] = Math.max(f[i][j + 1], f[i + 1][j]);
                }
            }
        }
        return f[m][n];
    }
    */

    /**
     * 两个数组
     */
    /*
    public int longestCommonSubsequence(String text1, String text2) {
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();
        int m = char1.length;
        int n = char2.length;
        int[][] f = new int[2][n + 1];
        f[0][0] = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (char1[i] == char2[j]) {
                    f[(i + 1) % 2][j + 1] = f[i % 2][j] + 1;
                } else {
                    f[(i + 1) % 2][j + 1] = Math.max(f[i % 2][j + 1], f[(i + 1) % 2][j]);
                }
            }
        }
        return f[m % 2][n];
    }
    */

    /**
     * 一个数组
     * 首先现在情况是
     * f[i][j] 还有
     * f[i + 1][j + 1] = Math.max(f[i][j + 1], f[i + 1][j]);
     * 所处位置分别是 左上 上 左 无法单纯用倒序或者正序就可以解决
     * 所以我们还需要引入一个变量pre 来记录当前i左侧的值 那么剩下的就可以用正序
     * 这里的区分点在于f[i + 1][j + 1] = f[i][j] + 1;  这里的f[i][j] 是要进行替换成pre的 因为他是当前i+1的对应的i行的左侧 属于倒序
     * 而f[i + 1][j + 1] = Math.max(f[i][j + 1], f[i + 1][j]); 里的f[i][j + 1]，f[i + 1][j] 都是符合正序的原则，无需替换
     */
    public int longestCommonSubsequence(String text1, String text2) {
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();
        int m = char1.length;
        int n = char2.length;
        int[] f = new int[n + 1];
        f[0] = 0;
        for (int i = 0; i < m; i++) {
            int pre = 0;// f[0]
            for (int j = 0; j < n; j++) {
                int temp = f[j + 1];
                if (char1[i] == char2[j]) {
                    f[j + 1] = pre + 1;
                } else {
                    f[j + 1] = Math.max(f[j + 1], f[j]);
                }
                pre = temp;
            }
        }
        return f[n];
    }
}
